home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / info-service / gopher / Unix / GopherTools / jughead / jughead.0.9 / dirTree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-21  |  11.8 KB  |  349 lines
  1. /*****************************************************************************
  2.  * File:    dirTree.c
  3.  *
  4.  * Author:    Rhett "Jonzy" Jones
  5.  *        jonzy@cc.utah.edu
  6.  *
  7.  * Date:    March 26, 1993
  8.  *
  9.  * Modified:    March 27, 1993, by Rhett "Jonzy" Jones.
  10.  *        Made the local variable 'strs' global to this file to reduce
  11.  *        the amount of stack space used when calling recursive routines.
  12.  *        Swapped the values of SSTR and PSTR so the tree will now be
  13.  *        built with the port as the initial tree and the selector string
  14.  *        as the last tree.  This was done to reduce the amount of memory
  15.  *        used by the tree itself.
  16.  *
  17.  *        March 30, 1993, by Rhett "Jonzy" Jones.
  18.  *        Added PrintDirTree().
  19.  *        Fixed that damn bug in BuildDirTree() that built the tree wrong.
  20.  *        'dTree' is NOT the same as 'node'...  dah!
  21.  *
  22.  *        April 1, 1993, by Rhett "Jonzy' Jones.
  23.  *        Modified PrintDirTree() and added the routine NumberOfDirs() to
  24.  *        support the -a and -A options.
  25.  *
  26.  * Description:    Contains tree routines for use with keeping track of directory
  27.  *        items encountered.  The tree structure is such that each node
  28.  *        contains the line number the directory was printed on if the
  29.  *        node contains the selector string, otherwise the value is -1, a
  30.  *        string representing the port, host, or selector string.  The purpose
  31.  *        of this code is to prevent retraversing a pretraveresed gopher
  32.  *        directory item.  No sense in traversing a directory more than once.
  33.  *        Fred Barrie says "some gopher administrators don't like to have
  34.  *        their server treed".  Thus the reason for keeping the traversing
  35.  *        to a mimimum.
  36.  *
  37.  *        To summarize: we build 3 level tree with level, the base,
  38.  *        sorted on the port, the second level of the tree is sorted
  39.  *        on host, and the last level is sorted on selector string.
  40.  *        The tree is built in this fashion to mimimize the impact on
  41.  *        memory.  With less ports being used in gopher space than hosts,
  42.  *        and less hosts than documents or directories being served, I
  43.  *        opted to to sort on port first.  Thus if all gopher space uses
  44.  *        port 70 tree, the base tree or level one only has one node.
  45.  *
  46.  * Routines:    static    long        NumberOfDirs(DirTreeType *node);
  47.  *            void        PrintDirTree(DirTreeType *dTree,short whichStr);
  48.  *            long        InDirTree(DirTreeType *dTree,short whichStr);
  49.  *            DirTreeType *WhatDirBranch(DirTreeType *dTree,short whichStr);
  50.  *        static    DirTreeType *CreateDirBranch(long lineNum,short whichStr);
  51.  *        static    DirTreeType *CreateDirNode(long lineNum,short whichStr);
  52.  *            DirTreeType *BuildDirTree(DirTreeType *dTree);
  53.  *            void        WaterTree(char *sStr,char *hStr,char *pStr);
  54.  *
  55.  * Bugs:    No known bugs.
  56.  *
  57.  * Copyright:    Copyright 1993, University of Utah Computer Center.
  58.  *        This source may be freely distributed as long as this copyright
  59.  *         notice remains intact, and is in no way used for any monetary
  60.  *         gain, by any institution, business, person, or persons.
  61.  *
  62.  * TODO:    Consolidate these routines into tree.c.  Many of the
  63.  *        routines in this file are very similar to those in tree.c.
  64.  *
  65.  ****************************************************************************/
  66.  
  67. #include <stdio.h>
  68. #include <stdlib.h>
  69. #include <string.h>
  70. #include "dirTree.h"
  71. #include "utils.h"
  72.  
  73. #define NIL        (void *)0L
  74.  
  75. /* These are also defined in "tree.h". */
  76. #define GOLEFT    -1
  77. #define THISONE    0
  78. #define GORITE    1
  79.  
  80. /* This is also defined in "jughead.c". */
  81. #define EMPTYSTRING    ""            /* The empty C string. */
  82.  
  83.     DirTreeType    *dirRoot = (DirTreeType *)NIL;
  84.     long        lineNumber = 0;
  85.     char        *strs[STRS];
  86. static    DirTreeType    *lastDirNode = (DirTreeType *)NIL;
  87. static    short        limb;
  88.  
  89. /* The following is defined in "jughead.c". */
  90. extern int    debug,                /* Are we debugging? */
  91.         printDTreeDirs;            /* Do we print the directories? */
  92.  
  93. #if(1)
  94. /* Also defined in "tree.c". */
  95. /*****************************************************************************
  96.  * WhatDirection returns GOLEFT if 's1' is less than 's2', returns GORITE if
  97.  * if 's1' is greater than 's2', or returns THISONE if 's1' is the same as
  98.  * 's2'.
  99.  ****************************************************************************/
  100. static short WhatDirection(s1,s2)
  101.     char    *s1,            /* String contained in the leaf. */
  102.         *s2;            /* String we are looking for. */
  103. {    short    direction;        /* What direction do we look? */
  104.  
  105.     if ((direction = strcmp(s1,s2)) < 0)
  106.         return(GOLEFT);
  107.     else if (direction > 0)
  108.         return(GORITE);
  109.     else
  110.         return(THISONE);
  111.  
  112. }    /* WhatDirection */
  113. #endif
  114.  
  115. /*****************************************************************************
  116.  * NumberOfDirs returns the nuber of the leaves contained in the tree 'node'.
  117.  ****************************************************************************/
  118. static long NumberOfDirs(node)
  119.     DirTreeType    *node;        /* The node to have summed. */
  120. {
  121.     if (!node)
  122.         return(0);
  123.     else
  124.         return(1 + NumberOfDirs(node->left) + NumberOfDirs(node->right));
  125.  
  126. }    /* NumberOfDirs */
  127.  
  128. /*****************************************************************************
  129.  * PrintDirTree prints the contents of the tree in a format depending on the
  130.  * 'debug' and 'printDTreeDirs' variables.  Basicly the format is:
  131.  * port1
  132.  *    host1
  133.  *        selectorString1
  134.  *        ...
  135.  *        selectorStringN
  136.  *    ...
  137.  *    hostN
  138.  * ...
  139.  * portN
  140.  ****************************************************************************/
  141. void PrintDirTree(dTree,whichStr)
  142.     DirTreeType    *dTree;
  143.     short        whichStr;
  144. {    short        i;
  145.  
  146.     if (dTree)
  147.         {
  148.         PrintDirTree(dTree->left,whichStr);
  149.  
  150.         /* Give some indention. */
  151.         for (i = PSTR; i < whichStr; i++)
  152.             fprintf(stdout,"\t");
  153.         if (whichStr < SSTR)
  154.             {
  155.             if (printDTreeDirs)
  156.                 if (debug)
  157.                     fprintf(stdout,"<see line %8ld>\t%s",dTree->lineNum,dTree->str);
  158.                 else
  159.                     fprintf(stdout,"\t%s",dTree->str);
  160.             else
  161.                 fprintf(stdout,"%ld %s accesed via: %s",NumberOfDirs(dTree),
  162.                         (whichStr == PSTR) ? "port(s)" : "host(s)",
  163.                         dTree->str);
  164.             if (whichStr == HSTR && !printDTreeDirs)
  165.                 fprintf(stdout," serving %ld directories\n",NumberOfDirs(dTree->tree));
  166.             else
  167.                 {
  168.                 fprintf(stdout,"\n");
  169.                 PrintDirTree(dTree->tree,whichStr + 1);
  170.                 }
  171.         }
  172.         else if (printDTreeDirs)
  173.             fprintf(stdout,"<see line %8ld>\t[%s]\n",dTree->lineNum,dTree->str);
  174.  
  175.         PrintDirTree(dTree->right,whichStr);
  176.         }
  177.  
  178. }    /* PrintDirTree */
  179.  
  180. /*****************************************************************************
  181.  * InDirTree returns the line number the data was previously encountered if
  182.  * the data has been seen before and false otherwise.
  183.  ****************************************************************************/
  184. long InDirTree(dTree,whichStr)
  185.     DirTreeType    *dTree;        /* The tree we are looking at. */
  186.     short        whichStr;    /* Index into array 'strs'. */
  187. {    int        result;        /* Result of calling strcmp(). */
  188.  
  189.     if (!dTree || whichStr > SSTR)
  190.         return(0);
  191.     else if (!(result = strcmp(strs[whichStr],dTree->str)))
  192.         if (whichStr == SSTR)
  193.             return(dTree->lineNum);
  194.         else
  195.             return(InDirTree(dTree->tree,whichStr + 1));
  196.     else if (result < 0)
  197.         return(InDirTree(dTree->left,whichStr));
  198.     else
  199.         return(InDirTree(dTree->right,whichStr));
  200.  
  201. }    /* InDirTree */
  202.  
  203. /*****************************************************************************
  204.  * WhatDirBranch returns the limb of the tree containing string indexed by
  205.  * 'whichStr.  This routine also assigns to 'limb' the direction we are
  206.  * looking in the tree and assigns to 'lastDirNode' the last node encountered.
  207.  * These assignments are done to speed the time required when building the tree.
  208.  ****************************************************************************/
  209. DirTreeType *WhatDirBranch(dTree,whichStr)
  210.     DirTreeType    *dTree;        /* The tree we are looking at. */
  211.     short        whichStr;    /* Index into the array 'strs'. */
  212. {
  213.     if (!dTree)        /* Insert at last position. */
  214.         return(dTree);
  215.     else switch (WhatDirection(strs[whichStr],dTree->str))
  216.         {
  217.         case GOLEFT:
  218.             limb = GOLEFT;
  219.             lastDirNode = dTree;
  220.             return(WhatDirBranch(dTree->left,whichStr));
  221.         case GORITE:
  222.             limb = GORITE;
  223.             lastDirNode = dTree;
  224.             return(WhatDirBranch(dTree->right,whichStr));
  225.         case THISONE:
  226.             return(dTree);
  227.         }
  228.     return((DirTreeType *)NIL);    /* Should never get here. */
  229.  
  230. }    /* WhatDirBranch */
  231.  
  232. /*****************************************************************************
  233.  * CreateDirBranch returns a node for the dTree containing 'str', and
  234.  * 'lineNum', with all other pointers set to nil.
  235.  ****************************************************************************/
  236. static DirTreeType *CreateDirBranch(lineNum,whichStr)
  237.     long        lineNum;    /* The line 'str' is from. */
  238.     short        whichStr;    /* Index into the array 'strs'. */
  239. {    DirTreeType    *node;        /* The node we are creating. */
  240.  
  241.     if (node = (DirTreeType *)malloc(sizeof(DirTreeType)))
  242.         if (node->str = (char *)malloc(strlen(strs[whichStr]) + 1))
  243.             {
  244.             if (whichStr == SSTR)
  245.                 node->lineNum = lineNum;
  246.             else
  247.                 node->lineNum = -1;
  248.             strcpy(node->str,strs[whichStr]);
  249.             node->left = node->right = node->tree = (DirTreeType *)NIL;
  250.             }
  251.         else
  252.             {
  253.             free(node);
  254.             node = (DirTreeType *)NIL;
  255.             fprintf(stderr,"error: CreateDirBranch could not get memory for the string [%s].\n",strs[whichStr]);
  256.             }
  257.     else
  258.         fprintf(stderr,"error: CreateDirBranch could not get memory for the node.\n");
  259.  
  260.     return(node);
  261.  
  262. }    /* CreateDirBranch */
  263.  
  264. /*****************************************************************************
  265.  * CreateDirNode returns a node for use in the 3 tiered tree.  This node
  266.  * may or may not contain all 3 trees.  This is dependent on the value of
  267.  * 'whichStr', which indexes into the array 'strs' telling us what string
  268.  * item we are processing.
  269.  ****************************************************************************/
  270. static DirTreeType *CreateDirNode(lineNum,whichStr)
  271.     long        lineNum;    /* The line 'strs' are from. */
  272.     short        whichStr;    /* Index into the array 'strs'. */
  273. {    DirTreeType    *node;        /* The node we are creating. */
  274.  
  275.     if (node = CreateDirBranch(lineNum,whichStr++))
  276.         if (whichStr < STRS)
  277.             if (node->tree = CreateDirBranch(lineNum,whichStr++))
  278.                 if (whichStr < STRS)
  279.                     if (node->tree->tree = CreateDirBranch(lineNum,whichStr++))
  280.                         return(node);
  281.                     else
  282.                         fprintf(stderr,"error: CreateDirNode failed.\n");
  283.                 else
  284.                     return(node);
  285.             else
  286.                 fprintf(stderr,"error: CreateDirNode failed.\n");
  287.         else
  288.             return(node);
  289.     else
  290.         fprintf(stderr,"error: CreateDirNode failed.\n");
  291.     return((DirTreeType *)NIL);
  292.  
  293. }    /* CreateDirNode */
  294.  
  295. /*****************************************************************************
  296.  * BuildDirTree returns the root of the 3 tiered tree, and adds the strings
  297.  * indexed by 'whichStr' to the proper branch of the tree.
  298.  ****************************************************************************/
  299. DirTreeType *BuildDirTree(dTree)
  300.     DirTreeType    *dTree;        /* The tree we are processing. */
  301. {    DirTreeType    *node;        /* The node we are adding. */
  302.     short        whichStr;    /* Index into the array 'strs'. */
  303.  
  304.     if (!dTree)
  305.         return(CreateDirNode(lineNumber,PSTR));
  306.  
  307.     if (node = WhatDirBranch(dTree,whichStr = PSTR))
  308.         if (node = WhatDirBranch(node->tree,whichStr = HSTR))
  309.             if (node = WhatDirBranch(node->tree,whichStr = SSTR))
  310.                 return(dTree);    /* Allready in the tree. */
  311.  
  312.     node = CreateDirNode(lineNumber,whichStr);
  313.     switch (limb)
  314.         {
  315.         case GOLEFT:
  316.             lastDirNode->left = node;
  317.             break;
  318.         case GORITE:
  319.             lastDirNode->right = node;
  320.             break;
  321.         }
  322.  
  323.     return(dTree);
  324.  
  325. }    /* BuildDirTree */
  326.  
  327. /*****************************************************************************
  328.  * WaterTree prepares BuildDirTree() and InDirTree() to either search or
  329.  * build on 'sStr', 'hStr', or 'pStr, by initializing the array 'strs',
  330.  * 'limb', and 'lastDirNode'.
  331.  ****************************************************************************/
  332. void WaterTree(sStr,hStr,pStr)
  333.     char    *sStr,        /* The selector string. */
  334.         *hStr,        /* The host string. */
  335.         *pStr;        /* The port string. */
  336. {
  337.  
  338.     strs[DSTR] = EMPTYSTRING;
  339.     strs[SSTR] = sStr;
  340.     strs[HSTR] = hStr;
  341.     strs[PSTR] = pStr;
  342.  
  343.     /* These don't realy need to be initializes because WhatDirBranch()    *
  344.      * assigns these variable to the proper value.  Better safe then sorry.    */
  345.     limb = 0;
  346.     lastDirNode = (DirTreeType *)NIL;
  347.  
  348. }    /* WaterTree */
  349.